package com.zp.self.module.level_4_算法练习.数学.数学推理;

import org.junit.Test;

/**
 * @author By ZengPeng
 */
public class 力扣_812_最大三角形面积 {
    @Test
    public void main() {

        System.out.println(largestTriangleArea(new int[][]{{0,0},{0,1},{1,0},{0,2},{2,0}}));
    }

    /**
    题目：给定包含多个点的集合，从其中取三个点组成三角形，返回能组成的最大三角形的面积。
     示例:
     输入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
     输出: 2
     解释:
     这五个点如下图所示。组成的橙色三角形是最大的，面积为2。

    分析：【BR 💔💔💔】
       1.数学推理：3个坐标求面积，需要将3个点向x轴作辅助点，得到3个梯形。
                    三角形面积 =  两个梯形面积和 - 另一个面积
    边界值 & 注意点：
       1.
     **/
    public double largestTriangleArea(int[][] points) {
        int len = points.length;
        double max=0;
        for (int i = 0; i < len-2; i++) {
            for (int j = i+1; j < len-1; j++) {
                for (int k = j+1; k < len; k++) {
                    int[] point1 = points[i];
                    int[] point2 = points[j];
                    int[] point3 = points[k];
                    int x1 = point1[0], y1 = point1[1];
                    int x2 = point2[0], y2 = point2[1];
                    int x3 = point3[0], y3 = point3[1];
                    max = Math.max(max, 0.5 * Math.abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)));
                }
            }

        }

        return 0;
    }
}